第十章测试题 20200112
看清是时间复杂度还是空间复杂度
做题不会
9
（）方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。（2.2 分）
- A、
[选择排序](javascript:void(0);) - B、
[快速排序](javascript:void(0);) - C、
[插入排序](javascript:void(0);) - D、
[归并排序](javascript:void(0);)
B。百度说 B。肯定不是归并，他不是交换的，肯定不是选择和插入，因为不是一次性的。
12
若对一组记录（76，38，62，53，80，74，83，65，85）进行堆排序，已知除第一个元素外，以其余元素位根的结点都已是堆，则对第一个元素进行筛运算时，它将最终被筛到下标为（）的位置。（2.2 分）
- A、
[7](javascript:void(0);) - B、
[8](javascript:void(0);) - C、
[6](javascript:void(0);) - D、
[9](javascript:void(0);)
B。感觉他没说清楚下标，他不说，默认 0 开始，查了答案也是 B。小根堆啊
34
设一组初始记录关键字序列为 (278,109,063,930,589,184,505,269,008,083) 经过第二趟分配和收集后得到的关键字序列为（）（2.2 分）
- A、
[930，063，083，184，505，278，008，109，589，269](javascript:void(0);) - B、
[505，008，109，930，063，269，278，083，184，589](javascript:void(0);) - C、
[930,083,063,184,505,008,278,269,589,109](javascript:void(0);) - D、
[008，063，083，109，184，269，278，505，589，930](javascript:void(0);)
B。相当于只看后面两位
41
设一组初始记录关键字序列为 (Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（）。（2.2 分）
- A、
[P，A，C，S，Q，D，F，X，R，H，M，Y](javascript:void(0);) - B、
[F，H，C，D，P，A，M，Q，R，S，Y，X](javascript:void(0);) - C、
[A，D，C，R，F，Q，M，S，Y，P，H，X](javascript:void(0);) - D、
[H，C，Q，P，A，M，S，R，D，F，X，Y](javascript:void(0);)
D。从前向后从后向前都试一试，这题只能从前向后
44
对一个由 n 个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数最少，应选用（）方法。
（2.2 分）
- A、
[快速排序](javascript:void(0);) - B、
[归并排序](javascript:void(0);) - C、
[直接插入排序](javascript:void(0);) - D、
[直接选择排序](javascript:void(0);)
D。百度说 D，确实只遍历一边就可以
第三次
28
在利用快速排序方法对一组记录（50，40，95，20，15，70，60，45，80）进行快速排序后递归调用使用的栈所能达到的最大深度为 2,其需递归调用的次数为（）。
（2.2 分）
- A、
[4](javascript:void(0);) - B、
[1](javascript:void(0);) - C、
[2](javascript:void(0);) - D、
[3](javascript:void(0);)
正确答案：A
题目：【填空题】19.在利用快速排序方法对一组记录 (50,40,95,20,15,70,60,45,80) 进行快速排序后,递归调用使用的栈所能达到的最大深度为 ,需递归调用的次数为 ,其中第二次递归调用是对 组记录进行快速排序。
答案：["2","4","(20,40,15)"]
第四次
39
在排序过程中，键值比较的次数与初始序列的排列顺序无关的是（）
（2.2 分）
- A、
[快速排序和归并排序](javascript:void(0);) - B、
[直接插入排序和归并排序](javascript:void(0);) - C、
[直接插入排序和快速排序](javascript:void(0);) - D、
[直接选择排序和归并排序](javascript:void(0);)
D。
我的错题
第一次
27
在最坏情况下（如初始记录已有序），快速排序的空间复杂性为（）；
（2.2 分）
0.0分
- A、
[O（n）](javascript:void(0);) - B、
- C、
- D、
我的答案：D
正确答案：A
空间复杂性啊兄弟
第二次
23
用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：
15，21，25，47，27，68，35，84
20，21，25，35，27，47，68，84
20，21，25，27，35，47，68，84
（2.2 分）
0.0分
- A、
[选择排序](javascript:void(0);) - B、
[快速排序](javascript:void(0);) - C、
[希尔排序](javascript:void(0);) - D、
[归并排序](javascript:void(0);)
我的答案：B
正确答案：？？
这什么，连序列都没给全，而且给全了也只能是快速排序
14
设一组初始记录关键字序列为 (278,109,063,930,589,184,505,269,008,083) 经过第一趟分配和收集后得到的关键字序列为（）（2.2 分）
0.0分
- A、
[505，008，109，930，063，269，278，083，184，589](javascript:void(0);) - B、
[930，063，083，184，505，278，008，109，589，269](javascript:void(0);) - C、
[930,083,063,184,505,008,278,269,589,109](javascript:void(0);) - D、
[008，063，083，109，184，269，278，505，589，930](javascript:void(0);)
我的答案：A
正确答案：B
看题啊一趟！！！！
第四次
20
若对一组记录（46，79，56，38，40，80，35，50，74）进行直接插入排序，当把第 8 个记录插入到前面已排序的有序表时，为寻找插入位置需比较 () 次。（2.2 分）
0.0分
- A、
[4](javascript:void(0);) - B、
[7](javascript:void(0);) - C、
[5](javascript:void(0);) - D、
[6](javascript:void(0);)
我的答案：C
正确答案：A
从有序序列的末尾开始向前逐个比对。
真的错题
第二次
23
用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：
15，21，25，47，27，68，35，84
20，21，25，35，27，47，68，84
20，21，25，27，35，47，68，84
（2.2 分）
0.0分
- A、
[选择排序](javascript:void(0);) - B、
[快速排序](javascript:void(0);) - C、
[希尔排序](javascript:void(0);) - D、
[归并排序](javascript:void(0);)
我的答案：B
正确答案：？？
这什么，连序列都没给全，而且给全了也只能是快速排序
第三次
15
在归并排序中，若待排序记录的个数为 20，则共需要进行 5 趟归并，在第 3 趟归并中，是把长度为 4 的有序表归并为长度为 () 的有序表。
（2.2 分）
2.2分
- A、
[4](javascript:void(0);) - B、
[8](javascript:void(0);) - C、
[5](javascript:void(0);) - D、
[7](javascript:void(0);)
我的答案：A
复习题遇到过，错题，8 不对